package com.heima.leetcode.practice;

import java.util.HashMap;

/**
 * leetcode 26 删除有序数组中的重复项
 * @author 勾新杰
 * @version 1.0
 * @date 2024/10/28 10:28
 */
public class E26 {

    /**
     * <h3>方法一：hashmap</h3>
     * @param nums nums数组
     * @return 删除重复元素后的数组长度
     */
    public int removeDuplicates1(int[] nums) {
        int index = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            Integer v = map.get(num);
            if (v == null){
                map.put(num, num);
                nums[index++] = num;
            }
        }
        return index;
    }

    /**
     * <h3>方法二：利用非严格递增的特性</h3>
     * @param nums nums数组
     * @return 删除重复元素后的数组长度
     */
    public int removeDuplicates2(int[] nums) {
        int removedBound = 0; // 删除重复元素后，数组中元素的右边界（包含）
        for (int i = 1; i < nums.length; i++) {
            if (nums[removedBound] != nums[i]){ // 如果处理好部分的右边界元素不等于当前遍历到的
                nums[++removedBound] = nums[i]; // 扩展边界
            }
        }
        return removedBound + 1;
    }
}
